# 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。 
# 
#  
# 
#  示例 1： 
#  
#  
# 输入：head = [1,2,3,4,5], k = 2
# 输出：[4,5,1,2,3]
#  
# 
#  示例 2： 
#  
#  
# 输入：head = [0,1,2], k = 4
# 输出：[2,0,1]
#  
# 
#  
# 
#  提示： 
# 
#  
#  链表中节点的数目在范围 [0, 500] 内 
#  -100 <= Node.val <= 100 
#  0 <= k <= 2 * 10⁹ 
#  
# 
#  Related Topics 链表 双指针 👍 1108 👎 0
from typing import Optional

from LeetCode.Test.LinkTool import ListNode, LinkedListTool, Link


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        cur = head
        size = 1
        if not cur:
            return head
        while cur.next:
            size += 1
            cur = cur.next

        k %= size
        curr = head
        if k==0:
            return head
        # 找到移动后的最后以一个节点
        for i in range(size - 1 - k):
            curr = curr.next
        # print(curr.val)

        new_head = curr.next
        f = new_head
        for _ in range(k-1):
            f=f.next
        f.next = head
        curr.next = None
        return new_head


# leetcode submit region end(Prohibit modification and deletion)
head = Solution().rotateRight(LinkedListTool([1, 2]), 0)
Link.each(head)
